#include <iostream>
#include <list>

using namespace std;

int max(int in[],const int len){
    int tmp=0;
    for(int i=0;i<len;i++){
        if(in[i]>tmp){
            tmp=in[i];
        }
    }
    return tmp;
}

// 1位 %10
// 2位 /10%10
// 3位 /100%10

void one_radix_sort(int in[],const int len,int wei){
    int* buckets=new int[10];
    int* out=new int[len];
    int idx=0;
    for(int i=0;i<10;i++){
        buckets[i]=0;
    }
    for(int i=0;i<len;i++){
        idx=in[i]/wei%10;
        buckets[idx]++;
    }
    for(int j=1;j<10;j++){
        buckets[j]+=buckets[j-1];
    }
    for(int i=len-1;i>=0;i--){
        idx=in[i]/wei%10;
        out[buckets[idx]-1]=in[i];
        buckets[idx]=buckets[idx]-1;
    }
    for(int i=0;i<len;i++){
        in[i]=out[i];
    }
    delete buckets;
    delete out;
}

void show(int in[],const int len){
    for(int i=0;i<len;i++){
        cout<<in[i]<<" ";
    }
    cout<<endl;
}
// 0 1 2 0
// 0 1 3 3

void radix_sort(int in[],const int len){
    //求最大值，默认都是大于等于0的整数
    int max_element=max(in,len);
    int wei_num=0;
    //求最大位数
    while(max_element>0){
        max_element=max_element/10;
        wei_num++;
    }

    int tmp=1;
    for(int wei=1;wei<=wei_num;wei++){
        show(in,len);
        one_radix_sort(in,len,tmp);
        tmp=tmp*10;
    }
}

//采用list进行基数排序
void list_radix_sort(int in[],const int len){
    list<int> buckets[10];
    //求最大值，默认都是大于等于0的整数
    int max_element=max(in,len);
    int wei_num=0;
    //求最大位数
    while(max_element>0){
        max_element=max_element/10;
        wei_num++;
    }

    int tmp=1;
    int idx=0;
    for(int wei=1;wei<=wei_num;wei++){
        show(in,len);

        for(int j=0;j<len;j++){
            idx=in[j]/tmp%10;
            buckets[idx].push_back(in[j]);
        }
        int m=0;
        for(int k=0;k<10;k++){
            while(!buckets[k].empty()){
                in[m]=buckets[k].front();
                m++;
                buckets[k].pop_front();
            }
        }
        tmp=tmp*10;
    }

}

int main(){

    int a[12]={21,28,19,8,2678,28,90,78,117,65,999,1678};
    //radix_sort(a,12);
    list_radix_sort(a,12);
    for(int i=0;i<12;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;

}